package leetcode_top;
import java.util.*;
import org.junit.*;

import utils.BracketUtils;

public class Ex56 {
    class Solution {
        public int[][] merge(int[][] intervals) {
            // Arrays.sort(intervals, (n1, n2) -> {
            //     if (n1[0] != n2[0]) return n1[0] - n2[0];
            //     else return n1[1] - n2[1];
            // });

            Queue<int[]> queue = new PriorityQueue<>((n1, n2) -> {
                if (n1[0] != n2[0]) return n1[0] - n2[0];
                else return n1[1] - n2[1];
            });

            for (int i = 0; i < intervals.length; i++) {
                queue.offer(intervals[i]);
            }
            int[] a, b;
            List<int[]> res = new ArrayList<>();
            while (queue.size() > 1) {
                a = queue.poll();
                b = queue.peek();
                if (a[1] < b[0]) {
                    res.add(a);
                } else {
                    queue.poll();
                    queue.offer(new int[]{a[0], Math.max(a[1], b[1])});
                }
            }
            res.add(queue.peek());
            return res.toArray(new int[res.size()][]);
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[1,3],[2,6],[8,10],[15,18]]");
        System.out.println(Arrays.deepToString(s.merge(nums)));
    }
}
